package algorithm.disjoint.union;

/**
 * 项目名称: god
 * 包 名 称: algorithm.disjoint.union
 * 类 名 称: UnionFindQuickUnionRankPathSplit
 * 类 描 述: TODO
 * 创建时间: 2020/6/30 3:05 下午
 * 创 建 人: Justice
 * Quick Union - 基于rank的优化 - 路径分裂(Path Split)
 */
public class UnionFindQuickUnionRankPathSplit extends UnionFindQuickUnionRank {
    public UnionFindQuickUnionRankPathSplit(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            int p = parents[v];
            parents[v] = parents[parents[v]];
            v = p;
        }
        return v;
    }
}
